/*
 * @lc app=leetcode.cn id=1337 lang=golang
 * @lcpr version=30119
 *
 * [1337] 矩阵中战斗力最弱的 K 行
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start

type Node struct {
	Index int
	Count int
}

func kWeakestRows(mat [][]int, k int) []int {
	nrows, _ := len(mat), len(mat[0])
	nodes := make([]Node, nrows)
	for i := 0; i < nrows; i++ {
		nodes[i] = Node{Index: i, Count: sum(mat[i])}
	}
	sort.Slice(nodes, func(i, j int) bool {
		if nodes[i].Count == nodes[j].Count {
			return nodes[i].Index < nodes[j].Index
		}
		return nodes[i].Count < nodes[j].Count
	})

	result := make([]int, k)
	for i := 0; i < k; i++ {
		result[i] = nodes[i].Index
	}
	return result
}

func sum(row []int) int {
	s := 0
	for _, v := range row {
		s += v
	}
	return s
}

// @lc code=end

/*
// @lcpr case=start
// [[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]]\n3\n
// @lcpr case=end

// @lcpr case=start
// [[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]]\n2\n
// @lcpr case=end

*/

